package zuoshen_video2.dynamic;

import java.util.*;

import org.junit.Test;

public class CoinMethods {

    /*
     * 一个数组表示硬币，每个硬币可以使用无限次数，求组成目标的币值的方案数
     */

    Set<String> set = new HashSet<>();

    public int combine1(int[] nums, int target) {
        // return dfs(target, nums, set, new PriorityQueue<>());
        return dfs3(0, target, nums);
    }

    public int dfs(int cur, int[] nums, Set<String> methods, PriorityQueue<Integer> use) {
        if (cur == 0) {
            StringBuilder sb = new StringBuilder();
            Queue<Integer> queue = new PriorityQueue<>(use);
            while (!queue.isEmpty()) {
                sb.append(queue.poll() + "_");
            }
            if (!methods.contains(sb.toString())) {
                methods.add(sb.toString());
                return 1;
            } else {
                return 0;
            }
        }
        if (cur < 0)
            return 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(use);
            queue.add(nums[i]);
            res += dfs(cur - nums[i], nums, methods, queue);
        }
        return res;
    }

    @Test
    public void test1() {
        int[] nums = { 3, 5, 10, 2 };
        System.out.println(combine1(nums, 10));
    }

    public int dfs2(int idx, int cur, int[] nums) {
        if (idx == nums.length)
            return cur == 0 ? 1 : 0;
        if (cur < 0)
            return 0;
        // 可以选择当前元素，也可以跳过。
        return dfs2(idx, cur - nums[idx], nums) + dfs2(idx + 1, cur, nums);
    }

    public int dfs3(int idx, int cur, int[] nums) {
        if (idx == nums.length)
            return cur == 0 ? 1 : 0;
        if (cur < 0)
            return 0;
        // 可以选择当前元素，也可以跳过。
        int res = 0;
        for (int i = 0; nums[idx] * i <= cur; i++) {
            res += dfs3(idx + 1, cur - nums[idx] * i, nums);
        }
        return res;
    }

    @Test
    public void test2() {
        PriorityQueue<Integer> use = new PriorityQueue<>();
        use.add(1);
        use.add(2);
        use.poll();
        System.out.println(use);
    }

    public int combine2(int[] nums, int target) {
        int len = nums.length;
        int[][] f = new int[len + 1][target + 1];
        f[len][0] = 1; // 其他f[len][?] = 0

        for (int i = len - 1; i >= 0; i--) {
            for (int j = target; j >= 0; j--) {
                int v;
                for (int k = 0; (v = k * nums[i]) <= j; k++) {
                    f[i][j] += f[i + 1][j - v];
                }
            }
        }
        return f[0][target];
    }

    public int combine3(int[] nums, int target) {
        int len = nums.length;
        int[] f = new int[target + 1];
        f[0] = 1; // 其他f[len][?] = 0

        for (int i = len - 1; i >= 0; i--) {
            // for (int j = target; j >= 0; j--) {
            for (int j = 0; j < target + 1; j++) {
                int v;
                // for (int k = 0; (v = k * nums[i]) <= j; k++) {
                //     f[j] += f[j - v];
                // }
                if (j >= nums[i]) {
                    //若从左往右算，左边的f[i + 1][j - nums[i]] + f[i + 1][j] 就是f[i][j] 的值
                    f[j] += f[j - nums[i]];
                }
            }
        }
        return f[target];
    }

    @Test
    public void test3() {
        int[] nums = { 3, 5, 10, 2 };
        System.out.println(combine2(nums, 10));
        System.out.println(combine3(nums, 10));

    }
}
